package 二叉树;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;

public class NC14二叉树的之字遍历 {

    /**
     * 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
     * 例如：
     * 给定的二叉树是{3,9,20,#,#,15,7},
     * 该二叉树之字形层序遍历的结果是
     * [
     * [3],
     * [20,9],
     * [15,7]
     * ]
     */

    public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> lists=new ArrayList<>();

        if(root==null){
            return lists;
        }

        Deque<TreeNode> queue=new ArrayDeque<>();
        queue.addLast(root);
        boolean isLeftStart=true;

        while (!queue.isEmpty()){

            int count=queue.size();
            ArrayList<Integer> list=new ArrayList<>();
            while (count>0){
                TreeNode treeNode = queue.removeFirst();
                list.add(treeNode.val);
                if(treeNode.left!=null) {
                    queue.addLast(treeNode.left);
                }
                if(treeNode.right!=null) {
                    queue.addLast(treeNode.right);
                }
                count--;
            }
            if(!isLeftStart){
                Collections.reverse(list);
            }
            lists.add(list);
            isLeftStart=!isLeftStart;
        }


        return lists;
    }

}
